package Tree.BST;

/**
 * @ClassName: BinarySearchTree
 * @Description: 二叉搜索树
 * @author: wangz48
 * @date: 2022-1-5 11:10
 */
public class BinarySearchTree<E> {

    private  int size;
    private Node<E> root; //根节点

    /**
     * 节点类
     * @param <E>
     */
    private static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent; //父节点

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

    /**
     * 是否为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 参数检查
     */
    private void elementNotNullCheck(E element){
        if (element == null){
         throw  new IllegalArgumentException("element must not be null");
        }
    }

    /**
     * 添加元素
     */
    public void add(E element){
        elementNotNullCheck(element);
        //添加第一个节点(根)
        if (root == null){
            root = new Node<>(element,null);
            size++;
            return;
        }
        /**
         * 添加的不是第一个节点，需要比较
         * 1.找到父节点
         * 2.创建新节点
         * 3.parent.left = node 或者 parent.right = node
         * 遇到值相等的怎么办？？？
         *  1）.如果相等直接返回
         *  2）.覆盖旧的值
         */
        Node<E> node = root;
        int compare = 0;
        Node<E> parent = null;
        while(node != null) {
            compare = compare(element, node.element);
            //接受父节点
            parent = node;
            if (compare > 0) {
                //新元素比节点元素大，与右子节点比较
                node = node.right;
            } else if (compare < 0) {
                //新元素比节点元素小
                node = node.left;
            } else {
                //相等
                return;
            }
        }
        // 看看插入到父节点哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if(compare >0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;

    }

    /**
     * 比较两个节点
     * @param e1
     * @param e2
     * @return 0相等，
     *         >0 代表e1>e2
     *         <0,代表e1<e2
     */
    private int compare(E e1,E e2){
       return 0;
    }
}
